package com.base.leetcode;

/**
 * @Author: hdhao
 * @Create: 2023/4/5 - 14:33
 * @Version: v1.0
 */
//数组中的第K个最大元素
public class Leetcode215 {
    /*
        解题思路:
            1、向小顶堆放入前k个元素
            2、对于剩余元素
                若 <=堆顶元素,则略过
                若 >堆顶元素,则替换堆顶元素
            3、这样小顶堆始终保留的是目前为止,前K大的元素
            4、循环结束,堆顶元素即为第K大的元素
     */
    public int findKthLargest(int[] nums, int k) {
        MinHeap heap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {
                heap.replace(nums[i]);
            }
        }
        return heap.peek();
    }
}
